Before you turn this problem in, make sure everything runs as expected. First, restart the kernel (in the menubar, select Kernel$\rightarrow$Restart) and then run all cells (in the menubar, select Cell$\rightarrow$Run All).

Make sure you fill in any place that says YOUR CODE HERE or "YOUR ANSWER HERE", as well as your name and collaborators below:

HW0: Introductions¶

Setup, Prerequisites, and Classification¶

Due Date: Monday 9/3, 11:59PM¶

Course Policies¶

Here are some important course policies. These are also located at http://www.ds100.org/fa18/.

Collaboration Policy

Data science is a collaborative activity. While you may talk with others about the homework, we ask that you write your solutions individually. If you do discuss the assignments with others please include their names at the top of your notebook.

This Assignment¶

Welcome to DS100! Before we work our way through the data science lifecycle, we need to ground ourselves in some of the foundations of data science. This assignment will cover your working environment, test prerequisite understanding and help you create your (first?) classification model.

One of the purposes of this homework is to help you diagnose your preparedness for the course. You should ask yourself if the math questions are too challenging, or if the coding is confusing. The rest of this course will rely heavily on these foundations and this homework should not be too difficult to complete. If it is, consider reviewing supplementary material such as the DS100 textbook.

As you work through this assignment, you will learn:

• Python basics, like defining functions.
• How to use the numpy library to compute with arrays of numbers.
• Debugging in python and notebook using pdb
• Linear algebra, calculus, probability
• Basics of classification using KNN

Score breakdown¶

Running a Cell¶

Try running the following cell. If you are unfamiliar with Jupyter Notebooks consider skimming this tutorial or selecting Help -> User Interface Tour in the menu above.

Even if you are familiar with Jupyter, we strongly encourage you to become proficient with keyboard shortcuts (this will save you time in the future). To learn about keyboard shortcuts go to Help -> Keyboard Shortcuts in the menu above.

Here are a few we like:

1. ctrl+return : Evaluate the current cell
2. shift+return: Evaluate the current cell and move to the next
3. esc : command mode (may need to press before using any of the commands below)
4. a : create a cell above
5. b : create a cell below
6. dd : delete a cell
7. m : convert a cell to markdown
8. y : convert a cell to code

Testing your Setup¶

This cell should run without problems:

1: Prerequisites¶

Python¶

Python is the main programming language we'll use in the course. We expect that you've taken CS61A, CS8, or an equivalent class, so you should be able to explain the following cells. Run them and make sure you understand what is happening in each.

If this seems difficult, please review one or more of the following materials.

• Python Tutorial: Introduction to Python from the creators of Python.
• Composing Programs Chapter 1: This is more of a introduction to programming with Python.
• Advanced Crash Course: A fast crash course which assumes some programming background.

Mathematical Expressions¶

Note that the rocket icon indicates that you should just run the following cells.

Output and Printing¶

For Loops¶

List Comprehension¶

Defining Functions¶

Getting Help¶

Passing Functions as Values¶

Anonymous Functions and Lambdas¶

Recursion¶

Question 1¶

Question 1a¶

Write a function nums_reversed that takes in a positive integer n and returns a string containing the numbers 1 through n including n in reverse order, separated by spaces. For example:

>>> nums_reversed(5)
'5 4 3 2 1'

Note: The line raise NotImplementedError() indicates that the implementation still needs to be added. This is an exception derived from RuntimeError. Please comment out that line when you have implemented the function.

The code icon indicates that you should complete the following block of code.

Test your code in the cell below.

Question 1b¶

Write a function string_splosion that takes in a non-empty string like "Code" and returns a long string containing every prefix of the input. For example:

>>> string_splosion('Code')
'CCoCodCode'
>>> string_splosion('data!')
'ddadatdatadata!'
>>> string_splosion('hi')
'hhi'

Hint: Try to use recursion. Think about how you might answering the following two questions:

1. [Base Case] What is the string_splosion of the empty string?
2. [Inductive Step] If you had a string_splosion function for the first $n-1$ characters of your string how could you extend it to the $n^{th}$ character? For example, string_splosion("Cod") = "CCoCod" becomes string_splosion("Code") = "CCoCodCode".

Test your code in the cell below.

Question 1c¶

Write a function double100 that takes in a list of integers and returns True only if the list has two 100s next to each other.

>>> double100([100, 2, 3, 100])
False
>>> double100([2, 3, 100, 100, 5])
True

Question 1d¶

Recall the formula for population variance below:

$$\sigma^2 = \frac{\sum_{i=1}^N (x_i - \mu)^2}{N}$$

In this question, we'll ask you to compute the population variance of a given list by completing the functions below. For this portion, do not use built in numpy functions; we will use numpy to verify our code.

2: NumPy¶

The NumPy library lets us do fast, simple computing with numbers in Python. We assume you have already taken Data 8, so you should already be familiar with Numpy. We will not teach Numpy in the course.

You should be able to understand the code in the following cells. If not, review the following:

• DS100 Numpy Review
• Condensed Numpy Review
• The Official Numpy Tutorial
• The Data 8 Textbook Chapter on Numpy

Jupyter pro-tip: Pull up the docs for any function in Jupyter by running a cell with the function name and a ? at the end:

You can close the window at the bottom by pressing esc several times.

Another Jupyter pro-tip: Pull up the docs for any function in Jupyter by typing the function name, then <Shift>-<Tab> on your keyboard. Super convenient when you forget the order of the arguments to a function. You can press <Tab> multiple times to expand the docs.

Try it on the function below:

You can use the tips above to help you decipher the following code.

Question 2¶

To test your understanding of Numpy we will work through some basic image exercises. In the process we will explore visual perception and color.

Images are 2-dimensional grids of pixels. Each pixel contains 3 values between 0 and 1 that specify how much red, green, and blue go into each pixel.

We can create images in NumPy:

We can then use the scikit-image library to display an image:

We can read in image files using the skimage.io.imread method.

Note that in many image formats (e.g., JPEG) image values are numbers between 0 and 255 corresponding to a byte. Therefore we divide each pixel value by 255 to obtain numbers between 0 and 1.

Question 2a¶

Complete the following block of code to plot the Red, Green, and Blue color channels separately. The resulting images should appear in black and white.

• Hint: pic[:, :, 0] will slice the image to extract the red color channel. Plotting the resulting matrix will generate a black and white picture.*

Question 2b¶

Surprisingly the human eye doesn't see all colors equally. To demonstrate this we will study how blurring color channels affects image appearance. First, we will try to blur each color channel individually. Complete the following block of code using the skimage.filters.gaussian blurring function (read the docs) to render a blurry black and white image for each of the color channels. You should set the standard deviation of the Gaussian blurring kernel sigma to 10.

Question 2c¶

Using the following block of code:

pic_copy = pic.copy()
pic_copy[:, :, channel] = ...
skimage.io.imshow(pic_copy)

we can replace a color channel with a different black and white image. Complete the following block of code to render three different versions of the full color image with just one of the channels blurred.

Question 2d¶

Each image should appear slightly different. Which one is the blurriest and which is the sharpest? Write a short description of what you see in the cell below.

*This icon means you will need to write in text response in the cell below using English.

Hint: I observe ... . On possible explanation for this is ... .

3: Debugging and Testing¶

In this course, you will write a significant amount of code and inevitably encounter some bugs in the process. You should feel comfortable reading stack traces, debugging erroneous code, and testing the code you write.

Regarding debugging methods, we will be using pdb (Python Debugger), linked here: https://docs.python.org/3/library/pdb.html. pdb provides an interactive debugger for python programs and works within a notebook. It has a lot of useful features such as setting conditional breakpoints and single stepping at the source line level.

We will only be enforcing pdb on this first assignment. You can still use print statements or other methods of your choice on other assignments, although when the code becomes increasingly complex you may find it harder to debug without pdb.

Please walk through the debugging.ipynb before proceeding.

Question 3¶

The following blocks of code contains some errors. Find the bug and fix it in the same block so that the function does what it is expected to do. Feel free to create new cells to debug and test your code. Once you are confident that your code works, change the _debug to _fixed to run our tests.

• Hint: Try to use array operations to simplify your code.

Question 3a¶

Question 3b¶

Question 3c¶

4: Multivariable Calculus, Linear Algebra, and Probability¶

The following questions ask you to recall your knowledge of multivariable calculus, linear algebra, and probability. We will use some of the most fundamental concepts from each discipline in this class, so the following problems should at least seem familiar to you.

For the following problems, you should use LaTeX to format your answer. If you aren't familiar with LaTeX, not to worry. It's not hard to use in a Jupyter notebook. Just place your math in between dollar signs:

\$ f(x) = 2x \\$ becomes $ f(x) = 2x $.

If you have a longer equation, use double dollar signs:

\$\\$ \sum_{i=0}^n i^2 \$\\$ becomes:

$$ \sum_{i=0}^n i^2 $$.

Here are some handy notation:

For more about basic LaTeX formatting, you can read this article.

If you have trouble with these topics, we suggest reviewing:

• Khan Academy's Multivariable Calculus
• Khan Academy's Linear Algebra
• Khan Academy's Statistics and Probability

Question 4¶

Question 4a¶

Recall that summation (or sigma notation) is a way of expressing a long sum in a concise way. Let $a_1, a_2, ..., a_n \in \mathbb{R}$ and $x_1, x_2, ..., x_n \in \mathbb{R}$ be collections of real numbers. When you see $x_i$, you can think of the $i$ as an index for the $i^{th}$ $x$. For example $x_2$ is the second $x$ value in the list $x_1, x_2, ..., x_n$. We define sigma notation as follows:

$$ \sum_{i=1}^n a_i x_i = a_1 x_1 + a_2 x_2 + ... + a_n x_n $$

We commonly use sigma notation to compactly write the definition of the arithmetic mean (commonly known as the average):

$$ \bar{x} = \dfrac{1}{n} \left(x_1 + x_2 + ... + x_n \right) = \dfrac{1}{n} \sum_{i=1}^{n} x_i $$

For each of the statements below, either prove that it is true by using definitions or show that it is false by providing a counterexample.

Note: *This icon means you will need to write in text response in the cell below using English + $\LaTeX$.

Statement I¶

$\dfrac{\sum_{i=1}^{n} a_i x_i}{\sum_{i=1}^{n} a_i} = \sum_{i=1}^n x_i$

Statement II¶

$\sum_{i=1}^{n} x_1 = nx_1$

Statement III¶

$\sum_{i=1}^{n} a_3 x_i = n a_3 \bar{x} $

Statement IV¶

$\sum_{i=1}^{n} a_i x_i = n \bar{a} \bar{x} $

Note:

We can also generalize the summation concepts above to multiple indices: consider an array of values $x_{ij}$

$$ \begin{bmatrix} x_{1,1} & x_{1, 2} & ... & x_{1, n} \\ x_{2,1} & x_{2, 2} & ... & x_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{n,1} & x_{n, 2} & ... & x_{n, n} \\ \end{bmatrix} $$

By convention, the first index refers to the row and the second index references the column. e.g. $x_{2, 4}$ is the value in the second row and the fourth column. For multi-indexed arrays like this, we can write down the sum of all the values by evoking sigma notation multiple times:

\begin{align*} \sum_{i=1}^{n} \sum_{j=1}^{n} x_{i,j} &= \sum_{i=1}^{n} \left(\sum_{j=1}^{n} x_{i,j} \right) \\ &= \sum_{i=1}^{n} \left(x_{i,1} + x_{i,2} + ... + x_{i,n}\right) \\ &= \sum_{i=1}^{n} x_{i,1} + \sum_{i=1}^{n} x_{i,2} + ... + \sum_{i=1}^{n} x_{i,n} \\ &= \left(x_{1,1} + x_{1,2} + ... + x_{1,n}\right) + \left(x_{2,1} + x_{2,2} + ... + x_{2,n}\right) + ... + \left(x_{n,1} + x_{n,2} + ... + x_{n,n}\right) \\ &= x_{1,1} + x_{1,2} + ... + x_{1,n} + x_{2,1} + x_{2,2} + ... + x_{2,n} + ... + ... + x_{n,1} + x_{n,2} + ... + x_{n,n} \end{align*}

Question 4b¶

Manipulate the following expression to show that it can be written as a sum of powers of $x$ (e.g. $3x + 5x^2 + 8x^3$):

$$ \ln \left( 3 e^{2 x} e^{\frac{1}{x^2}} \right) $$

Question 4c¶

Suppose we have the following scalar-valued function on $x$ and $y$:

$$ f(x, y) = x^2 + 4xy + 2y^3 + e^{-3y} + \ln(2y) $$

Compute the partial derivative with respect to $x$.

Now compute the partial derivative of $f(x,y)$ with respect to $y$:

Question 4d¶

Find the value(s) of $x$ which minimize the expressions below. Justify why it is the minimum.

Part A¶

$\sum_{i=1}^{10} (i - x)^2$

Part B¶

$\sin\left(\frac{x}{2}\right)\cos\left(\frac{x}{2}\right)$

Part C¶

$ \vert 5 - x \vert + \vert 3 - x \vert + \vert 1 - x \vert $

Question 4e¶

Let $ \sigma(x) = \dfrac{1}{1+e^{-x}} $

Part A¶

Show that $\sigma(-x) = 1 - \sigma(x)$ where $\sigma(x) = \frac{1}{1+e^{-x}}$.

Part B¶

Show that the derivative can be written as:

$$\frac{d}{dx}\sigma(x) = \sigma(x)(1 - \sigma(x)) $$

Question 4f¶

Write code to plot the function $f(x) = x^2$ and the derivative of $f$ evaluated at $x=8$ and $x=0$.

Set the range of the x-axis to (-15, 15) and the range of the y axis to (-100, 300) and the figure size to (8,8).

Your resulting plot should look like this:

You should use the plt.plot function to plot lines. You may find the following functions useful:

• plt.plot
• plt.figure(figsize=..)
• plt.ylim(..)
• plt.axhline(..)

Question 4g¶

How can we interpret what the derivative of a function is using this plot?

Question 4h¶

Consider the following scenario:

Only $1\%$ of 40-year-old women who participate in a routine mammography test have breast cancer. $80\%$ of women who have breast cancer will test positive, but $9.6\%$ of women who don’t have breast cancer will also get positive tests.

Suppose we know that a woman of this age tested positive in a routine screening. What is the probability that she actually has breast cancer?

Hint: Try to use Bayes' rule.

5: Basic Classification¶

Suppose we have a dataset containing two different classes, class A and class B, visualized below as purple dots and yellow dots. Let's implement basic K nearest neighbors classifier that classifies a point of interest by finding the K nearest neighbors. Recall the K-NN algorithm:

Given an example point to classify and the population we are querying from,

1. Find the distance between the example point and each point in the data set

2. Augment the data table with a column containing all the distances to the example point

3. Sort the augmented table in increasing order of the distances to the example point

4. Take the top k rows of the sorted table to get the K nearest neighbors

Question 5¶

Fill in the functions distance and getNeighbors below, and test your code against the sklearn KNN classifier (write tests to see that your getNeighbors finds the same neighbors as the sklearn version). You must write at least 2 test cases with one example for each class.

Sklearn KNN: http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

If your code is written properly, the two plots below should plot the point of interest, example_A and example_B, (red) and the K nearest neighbors (green). It should look SIMILAR to the two plots below.

Submission¶

You're done!

Before submitting this assignment, ensure to:

1. Restart the Kernel (in the menubar, select Kernel->Restart & Run All)
2. Validate the notebook by clicking the "Validate" button

Finally, make sure to submit the assignment via the Assignments tab in Datahub